The present invention relates to a self-routing switch which is based on distributed control by hardware, such as an interconnection network for interprocessor communications in a computer or a switch for fast packet switching.
FIG. 1 shows a Banyan switch known as a typical self-routing switch, which is shown to be a simple eight-by-eight switch for convenience of description. An information data which this switch handles is appended with a bit string (a.sub.1, a.sub.2, a.sub.3) of routing information indicating the number of the output line to which the information data is to be transferred. In an ith stage (where i=1, 2, 3) switching takes place based on the bit a.sub.i of the routing information and the information data reaches the appointed output line after passage through all stages. For instance, a switch element 111-1 of the first stage transfers information data to a link 121-0 or 121-1 depending upon whether the bit a.sub.1 of the routing information (a.sub.1, a.sub.2, a.sub.3) of the information data, which is transferred from a link 120-0, is "0" or "1". A switch element 111-2 transfers information data to a link 121-2 or 121-3 depending upon whether the bit a.sub.1 is "0" or "1 ". Also in the other switch elements of the first stage the same operation is performed according to the bit a.sub.1. In second and third stages similar operations are repeated depending upon the bits a.sub.2 and a.sub.3 of the routing information (a.sub.1, a.sub.2, a.sub.3) of the information data, respectively. As a result of this, the information data is transferred to the specified output line. Let it be assumed that the routing information of the information data transferred from an input line (100) through a link 120-4 is (0, 1, 0), for example. Since the bit a.sub.1 is "0", a switch element 111-3 transfers the information date via a link 121-4 to a switch element 112-3; since the bit a.sub.2 is "1", the switch element 112-3 transfers the information data via a link 122-5 to a switch element 113-2; and since the bit a.sub.3 is a "0", the switch element 113-2 transfers the information data via a link 123-2 to the specified output line (010). This switch suffers from blocking because it provides only one routing path for each information data from one of the input lines to one of the output lines and a plurality of information data destined for different output lines may happen to pass through the same link. Accordingly, the switch becomes unable to perform routing operation in case of concentrated traffic. To avoid this, it is necessary to accelerate the link speed or increase the number of buffers in each switch element.
As a solution to this problem, there has been proposed a switch in which a sorting network 201 is provided at a stage preceding a routing network 204 as shown in FIG. 2 (A. Huang and S. Knauer, "STARLITE: A Wideband Digital Switch", AFIPS Conf. Proc' 84, 5, 3, 1-5.3.5). Reference numeral 202 indicates a comparator and 203 a trap circuit. The sorting network 201 checks the routing information appended to the information data and rearranges them in ascending or descending order of their output line numbers. The comparator 202 and the trap circuit 203 trap all information data having same routing information except for one of them to be transferred to the routing network 204 which may be of the type shown in FIG. 1. The information data thus trapped are applied again to the sorting network 201. In this way, the conventional switch prevents the occurrence of blocking.
With the prior art switch in which the sorting network 201 is provided at the stage preceding the routing network 204, however, letting the number of lines involved be represented by N, the scale of the routing network enlarges on the order of (N/2)log.sub.2 N and the scale of the sorting network enlarges on the order of (N/4) (log.sub.2 N) (log.sub.2 N+1); therefore, an enormous quantity of hardware will be needed when the number of lines N is large. Furthermore, many crossovers of links are involved, constituting an obstacle to fabrication of the switch as an LSI. In addition, the prior art switch has the defect that a delay time in switching undergoes substantial variations according to temporarily concentrated traffic on a certain output line.